package 剑指offer;

public class p68_II二叉树的最近公共祖先 {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root==null) {
            return null;
        }

        if (root.val==p.val || root.val==q.val) return root;

        TreeNode rootLeft=lowestCommonAncestor(root.left,p,q);
        TreeNode rootRight=lowestCommonAncestor(root.right,p,q);

        if (rootLeft!=null && rootRight!=null) {
            //p q 在当前根节点的左右子树中，最近公共祖先则为当前根节点
            return root;
        }else if (rootLeft==null) {
            //p q 不在当前根节点的左子树，最近公共祖先则rootRight中存的节点
            return rootRight;
        }else {
            //p q 不在当前根节点的右子树，最近公共祖先则rootLeft中存的节点
            return rootLeft;
        }

    }
}
